package LeetCode._02算法基础.day08广度深度优先搜索;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 20 - 10:04
 * @Description 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。
 * 如果不存在这样的路径，返回 -1 。
 * 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，
 * 该路径同时满足下述要求：
 * 路径途经的所有单元格都的值都是 0 。
 * 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
 * 畅通路径的长度 是该路径途经的单元格总数。
 * @Version 中等
 */
public class _1091二进制矩阵最短路径 {
    static int[][] grid = {
            {0 , 1},
            {1, 0}
    };
    @Test
    public void solve(){
        int res = shortestPathBinaryMatrix1(grid);
        System.out.println(res);
    }
    /*by me 深度优先搜索 超时*/
    int min = Integer.MAX_VALUE;
    int[][] direction = {
            {0, -1},
            {-1, -1},
            {-1, 0},
            {-1, 1},
            {0, 1},
            {1, 1},
            {1, 0},
            {1, -1}
    };
    public int shortestPathBinaryMatrix(int[][] grid) {
        dfs(grid, 0, 0, 1);
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public void dfs(int[][] grid, int i, int j, int step){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 0 || step > min)
            return;

        if(i == grid.length - 1 && j == grid[0].length - 1){
            min = Math.min(min, step);
            return;
        }
        int temp = grid[i][j];
        grid[i][j] = 2;
        for(int k = 0; k < direction.length; k++){
            dfs(grid, i + direction[k][0], j + direction[k][1], step + 1);
        }
        grid[i][j] = temp;
    }

    /*官方思路 广度优先搜索*/

    /*
    在二维矩阵中搜索，什么时候用BFS，什么时候用DFS？
    1.如果只是要找到某一个结果是否存在，那么DFS会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，
    只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，
    也尝试了很多不必要的路径；
    2.如果是要找所有可能结果中最短的，那么BFS回更高效。
    因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，
    才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，
    所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。
     */
    public int shortestPathBinaryMatrix1(int[][] grid) {
        int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,1},{1,-1}};
        int m = grid.length;
        int n = grid[0].length;
        //记录点是否走过
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int dis = 1;
        if (grid[0][0] != 0){
            return -1;
        }
        if (m == 1){
            return 1;
        }
        queue.offer(new int[]{0,0});
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int c = 0; c < size; ++c) {
                int[] poll = queue.poll();
                int i = poll[0];
                int j = poll[1];
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dir[k][0];
                    int nj = j + dir[k][1];
                    /*
                    如果在此之前某个点已经在visited中，也就是说有其他路径在小于或等于当前步数的情况下，
                    到达过这个点，证明到达这个点的最短路径已经被找到。那么显然这个点没必要再尝试了，
                    因为即便去尝试了，最终的结果也不会是最短路径了，所以直接放弃这个点即可。
                     */
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 0 && !vis[ni][nj]) {
                        if (ni == m - 1 && nj == n - 1) {
                            return dis + 1;
                        }
                        queue.offer(new int[]{ni, nj});
                        vis[ni][nj] = true;
                    }
                }
            }
            //这一圈都加1
            dis += 1;
        }
        return -1;
    }
}
